package homeWork2;

import java.security.spec.ECGenParameterSpec;
import java.util.*;


//添加要求，要求输入一个字符串看是否能被有限状态自动机接受
public class Main {

    public static NFA nfa;
    public static void main(String[] args) {
        String s = "(a|b)*abb";
        String suffixStr = suffixConversion(s);
        System.out.println(suffixStr);
        nfa = createNFA(suffixStr);
        nfa.setRelations(calculateRelations(s));
        System.out.println(nfa);

        System.out.println(determineNFA(nfa));
    }

    //判断优先级
    public static Integer priority(Character c){
        if (c == '*') return 3;
        else if (c == '.') return 2;
        else if (c == '|') return 1;
        else return 0;
    }

    //添加连接的符号
    public static String Construct_new_regular(String s){
        String res = "";
        for (int i = 0; i < s.length() - 1; i++){
            char c1 = s.charAt(i);
            char c2 = s.charAt(i + 1);
            boolean flag1 = c1 >= 'a' && c1 <= 'z';
            boolean flag2 = c2 >= 'a' && c2 <= 'z';
            res += c1;
            if(flag1 && flag2){
                res += '.';
                continue;
            }
            else if(c1 == ')' && flag2){
                res += '.';
                continue;
            }else if (c1 == '*' && flag2){
                res += '.';
                continue;
            }else if (c1 == ')' && c2 == '(')
            {
                res += '.';
                continue;
            }else if (c1 == '*' && c2 == '(')
            {
                res += '.';
                continue;
            }else if (flag1 && c2 == '('){
                res += '.';
            }
        }
        res += s.charAt(s.length() - 1);
        System.out.println(res);
        return res;
    }

    //转化为后缀表达式
    public static String suffixConversion(String s){
        s = Construct_new_regular(s);
        Stack<Character> op = new Stack<>();
        String res = "";
        int length = s.length();
        for (int i = 0; i < length; i++){
            char c = s.charAt(i);
            if (c == '('){
                op.push(c);
            }
            else if(c == ')'){
                while(op.peek() != '('){
                    res += op.peek();
                    op.pop();
                }
                op.pop();
            }
            else if (c == '*' || c == '|' || c == '.'){
                while (op.size() != 0){
                    if(priority(c) <= priority(op.peek())){
                        res += op.peek();
                        op.pop();
                    }
                    else break;
                }
                op.push(c);
            }
            else res += c;
        }

        while (op.size() != 0){
            res += op.peek();
            op.pop();
        }

        return res;
    }

    //是否是运算符
    public static Boolean isOp(Character c){
        if (c == '(' || c == '|' || c == ')' || c == '.' || c == '*')
            return true;
        else
            return false;
    }

    //计算关系数
    public static List<Character> calculateRelations(String str){
        ArrayList<Character> res = new ArrayList<>();
        for (int i = 0; i < str.length(); i++){
            if (!isOp(str.charAt(i))){
                if (!res.contains(str.charAt(i))){
                    res.add(str.charAt(i));
                }
            }
        }
        return res;
    }

    // 通过后缀表达式构建NFA
    public static NFA createNFA(String suffix){
        Stack<NFA> NStack = new Stack<>();
        Integer x = 0;
        for(int i = 0; i < suffix.length(); i++){
            Character c = suffix.charAt(i);
            if (!isOp(c)){
                //创建一个基础NFA加入NFA栈
                NFA.Node n1 = new NFA.Node(++x,1);
                NFA.Node n2 = new NFA.Node(++x,1);
                NFA.Edge edge = new NFA.Edge(n1, n2, c);
                ArrayList<NFA.Edge> edges = new ArrayList<>();
                edges.add(edge);
                NFA nfa = new NFA(n1,n2,null,edges);
                NStack.push(nfa);
            }
            else{
                switch (c){
                    case '.':
                    {
                        /*
                        * 连接合并
                        */
                        NFA n2 = NStack.peek();
                        NStack.pop();

                        NFA n1 = NStack.peek();
                        NStack.pop();

                        List<NFA.Edge> n2_Edge = n2.getEdges();
                        List<NFA.Edge> n1_Edge = n1.getEdges();
                        for (int j = 0; j < n2_Edge.size(); j++){
                            if (n2_Edge.get(j).getStart() == n2.getStart()){
                                n2_Edge.get(j).setStart(n1.getEnd());
                            }
                        }

                        for (int j = 0;j < n1_Edge.size(); j++){
                            n2_Edge.add(n1_Edge.get(j));
                        }

                        NFA nfa = new NFA(n1.getStart(), n2.getEnd(),null, n2_Edge);
                        NStack.push(nfa);
                        break;
                    }
                    case '|':{
                        /*
                        * 或运算
                        * */

                        NFA n2 = NStack.peek();
                        NStack.pop();

                        NFA n1 = NStack.peek();
                        NStack.pop();

                        List<NFA.Edge> n2_Edge = n2.getEdges();
                        List<NFA.Edge> n1_Edge = n1.getEdges();

                        NFA.Node start = new NFA.Node(++x, 1);
                        NFA.Node end = new NFA.Node(++x, 1);
                        NFA.Edge e1 = new NFA.Edge(start, n2.getStart(), 'ξ');
                        NFA.Edge e2 = new NFA.Edge(start, n1.getStart(), 'ξ');
                        NFA.Edge e3 = new NFA.Edge(n1.getEnd(), end, 'ξ');
                        NFA.Edge e4 = new NFA.Edge(n2.getEnd(), end, 'ξ');

                        for (int j = 0; j < n1_Edge.size();j++){
                            n2_Edge.add(n1_Edge.get(j));
                        }
                        n2_Edge.add(e1);
                        n2_Edge.add(e2);
                        n2_Edge.add(e3);
                        n2_Edge.add(e4);
                        NStack.push(new NFA(start,end,null,n2_Edge));
                        break;
                    }
                    case '*':{
                        NFA n1 = NStack.peek();
                        NStack.pop();

                        List<NFA.Edge> n1_Edge = n1.getEdges();

                        NFA.Node start = new NFA.Node(++x, 1);
                        NFA.Node end = new NFA.Node(++x, 1);

                        NFA.Edge e1 = new NFA.Edge(start, n1.getStart(), 'ξ');
                        NFA.Edge e2 = new NFA.Edge(n1.getEnd(), end, 'ξ');
                        NFA.Edge e3 = new NFA.Edge(n1.getEnd(),n1.getStart(),'ξ');
                        NFA.Edge e4 = new NFA.Edge(start,end,'ξ');

                        n1_Edge.add(e1);
                        n1_Edge.add(e2);
                        n1_Edge.add(e3);
                        n1_Edge.add(e4);

                        NStack.push(new NFA(start,end,null,n1_Edge));
                        break;
                    }
                }
            }
        }

        return NStack.peek();
    }

    // ξ闭包运算
    public static ArrayList<Integer> closures_ξ(List<Integer> list,NFA nfa){
        ArrayList<Integer> ans = new ArrayList<>();

        //建立搜寻队列
        Queue<Integer> queue = new LinkedList<Integer>();
        for (Integer i : list){
            queue.add(i);
            ans.add(i);
        }

        //开始搜寻
        while(!queue.isEmpty()){
            Integer front = queue.peek();
            queue.remove();
            for (NFA.Edge edge : nfa.getEdges()){
                if (edge.getRelations() == 'ξ' && edge.getStart().getID() == front){
                    if (!ans.contains(edge.getEnd().getID())){
                        //加入结果和搜寻队列
                        ans.add(edge.getEnd().getID());
                        queue.add(edge.getEnd().getID());
                    }
                }
            }
        }

        return ans;
    }

    // 弧转换
    public static ArrayList<Integer> conversionByArc(List<Integer> list, NFA nfa,Character relation){
        //创建搜寻队列
        Queue<Integer> queue = new LinkedList<>();
        //创建返回结果集
        ArrayList<Integer> ans = new ArrayList<>();

        //先将集合中的元素加入队列
        for (Integer i : list){
            queue.add(i);
        }

        //开始搜寻
        while (!queue.isEmpty()){
            //拿出队列头
            Integer front = queue.peek();
            queue.remove();

            for (NFA.Edge edge : nfa.getEdges()){
                //如果存在这个关系路径或者有ξ的关系
                if (edge.getStart().getID() == front && (edge.getRelations() == relation || edge.getRelations() == 'ξ')){
                    //判断这个节点是不是已经添加过了
                    if (!ans.contains(edge.getEnd().getID())){
                        //给返回的结果添加
                        ans.add(edge.getEnd().getID());
                        //加入搜索队列
                        queue.add(edge.getEnd().getID());
                    }
                }
            }
        }

        return ans;
    }

    //判断集合是否相同
    public static Boolean isSameArray(ArrayList<Integer> a,ArrayList<Integer> b){
        if (a.size() != b.size())
            return false;
        else {
            Collections.sort(a);
            Collections.sort(b);
            for (int i = 0; i < a.size(); i++){
                if (a.get(i) != b.get(i))
                    return false;
            }
        }
        return true;
    }

    // NFA确定化（子集法）
    public static NFA determineNFA(NFA nfa){
        //就是子集法表格的一个元素，不知道起啥名字了
        class Row{
            public ArrayList<Integer> nodeSet;
            public Integer ID;

            @Override
            public String toString() {
                return "Row{" +
                        "nodeSet=" + nodeSet +
                        ", ID=" + ID +
                        '}';
            }

            public Row() {
            }

            public Row(ArrayList<Integer> set, Integer ID) {
                this.nodeSet = set;
                this.ID = ID;
            }

            public ArrayList<Integer> getSet() {
                return nodeSet;
            }

            public void setSet(ArrayList<Integer> set) {
                this.nodeSet = set;
            }

            public Integer getID() {
                return ID;
            }

            public void setID(Integer ID) {
                this.ID = ID;
            }
        }

        Queue<Row> queue = new LinkedList<>();
        // 重命名的编号
        int index = 0;

        //开始节点
        ArrayList<Integer> startNode = new ArrayList<>();
        startNode.add(nfa.getStart().getID());

        //创建一个表格集合类
        Row row = new Row();
        row.setID(index++);
        row.setSet(closures_ξ(startNode,nfa));

        //返回的NFA
        NFA resNFA = new NFA();
        resNFA.setStart(new NFA.Node(row.getID(), 0));
        ArrayList<NFA.Edge> edges = new ArrayList<>();
        resNFA.setEdges(edges);
        resNFA.setRelations(nfa.getRelations());

        //节点集合
        ArrayList<Row> resNodes = new ArrayList<>();
        resNodes.add(row);
        queue.add(row);

        //开始用子集法化简
        while(!queue.isEmpty()){
            //拿出队列头部元素
            Row front = queue.peek();
            queue.remove();

            // 子集法
            for (Character relation : nfa.getRelations()){

                // 弧转换运算
                ArrayList<Integer> newRow = conversionByArc(front.nodeSet,nfa,relation);
                // 要是合集是空说明没有路径
                if (newRow.isEmpty())
                    continue;

                //建立一个临时变量，存储Row
                Row tempRow = new Row();
                //检验是否是出现过的集合，flag是标记
                int flag = 1;
                for (int i = 0; i < resNodes.size(); i++){
                    if (isSameArray(newRow,resNodes.get(i).getSet()))
                    {
                        //要是集合出现过，构建一个指向自己的关系，并且加入DFA中
                        flag = 0;
                        NFA.Edge edge = new NFA.Edge(new NFA.Node(front.getID(),1),new NFA.Node(resNodes.get(i).getID(),1),relation);
                        resNFA.getEdges().add(edge);
                        break;
                    }
                }

                // 要是集合是一个新集合，则加入队列
                if (flag == 1){
                    tempRow.setID(index++);
                    tempRow.setSet(newRow);
                    queue.add(tempRow);
                    resNodes.add(tempRow);

                    // 构建关系
                    NFA.Edge edge = new NFA.Edge(new NFA.Node(front.getID(), 1), new NFA.Node(tempRow.getID(), 1), relation);
                    resNFA.getEdges().add(edge);
                }
            }

            //判断一下要是队列为空，说明这个是终止节点
            if (queue.isEmpty()){
                resNFA.setEnd(new NFA.Node(front.getID(),-1));
            }
        }

        return resNFA;
    }
}
